package com.seatiger.structure.recursion;

import java.util.List;

/**
 * Given the head of a linked list and an integer val,
 * remove all the nodes of the linked list that has Node.val == val,
 * and return the new head.
 */
public class RemoveLinkedListElements {
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //使用虚拟头节点
    public ListNode removeElements2(ListNode head, int val) {
        ListNode dummyNode = new ListNode(0,head);
        ListNode pre = dummyNode;
        while (pre.next != null) {
            if (pre.next.val == val) {
                ListNode dealNode = pre.next;
                pre.next = dealNode.next;
                dealNode.next = null;
            }else {
                pre = pre.next;
            }
        }
        return dummyNode.next;
    }

    //不使⽤虚拟头结点
    public ListNode removeElements(ListNode head, int val) {
        //首先判断头节点是需要删除
        //删除之后，新的头节点，有可能也是需要删除，需要循环删除
        while (head != null && head.val == val) {
            ListNode dealNode = head;
            head = head.next;
            dealNode.next = null;
        }
        if (head == null) {
            return null;
        }

        ListNode pre = head;
        while (pre.next != null){
            //找到删除节点的前一个节点
            if (pre.next.val == val) {
                ListNode dealNode = pre.next;
                pre.next = dealNode.next;
                dealNode.next = null;
            }else {
                pre = pre.next;
            }
        }
        return head;
    }
}




